# Copyright 2007 Boris Dusek
#
# This file is part of grapy.
#
# Grapy is free software: you can redistribute it and/or modify
# it under the terms of the GNU General Public License as published by
# the Free Software Foundation, version 3 of the License.
#
# Grapy is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
# GNU General Public License for more details.
#
# You should have received a copy of the GNU General Public License
# along with Grapy.  If not, see <http://www.gnu.org/licenses/>.

from grapy.DFSHooks import DFSEnvironment

class Graph:

    def __init__(self, multi=False, directed=False):
        self.multi = multi
        self.directed = directed

    def init_from_graph(self, g):
        self.multi = g.multi
        self.directed = g.directed
        for u in g.vertices():
            self.add_vertex(u)
            for v in g.neighbours(u):
                self.add_edge((u,v))

    def add_edge(self, u, v):
        raise NotImplementedError

    def add_vertex(self, u):
        raise NotImplementedError

    def init_from_stream(self, stream):
        for line in stream:
            tokens = [token.strip() for token in line.split('-')]
            nTokens = len(tokens)
            if nTokens == 1:
                self.add_vertex(tokens[0])
            else:
                self.add_edge(tuple(tokens[0:2]))

    def V(self):
        raise NotImplementedError

    def E(self):
        raise NotImplementedError

    def degree_in(self, u):
        raise NotImplementedError

    def degree_out(self, u):
        raise NotImplementedError

    def transpose(self):
        raise NotImplementedError

    def unmulti(self):
        raise NotImplementedError

    def square(self):
        raise NotImplementedError

    def universal_sink(self):
        raise NotImplementedError

    def vertices(self):
        raise NotImplementedError

    def edges(self):
        raise NotImplementedError

    def neighbours(self, u):
        raise NotImplementedError

    def BFS(self, s):
        """Breadth-first search
        
        Returns shortest distances from s and parents in BFS tree"""

        c  = {}.fromkeys(self.vertices(), 0)
        d  = {}.fromkeys(self.vertices())
        p  = {}.fromkeys(self.vertices())
        Q = []

        d[s] = 0
        c[s] = 1
        Q.append(s)

        while Q:
            u = Q.pop(0)
            for v in self.neighbours (u):
                if c[v] == 0:
                    c[v] = 1
                    d[v] = d[u] + 1
                    p[v] = u
                    Q.append(v)
            c[u] = 2

        return d,p

    def print_shortest_path(self, s, u, p=None):
        if s == u:
            print s
        else:
            if not p:
                p = self.BFS(s)[1]
            self.print_shortest_path(s, p[u], p)
            print u

    def DFS(self,dfs_hooks,dfs_environ=DFSEnvironment()):
        dfs_environ.c  = {}.fromkeys(self.vertices(), 0)

        dfs_hooks.dfs_main_begin(dfs_environ)

        for u in dfs_hooks.dfs_main_vertices_order(dfs_environ,self.vertices()):
            if dfs_environ.c[u] == 0:
                dfs_hooks.dfs_main_visit_invoke_before(dfs_environ,u)
                self.DFS_visit(u,dfs_environ,dfs_hooks)
                dfs_hooks.dfs_main_visit_invoke_after(dfs_environ,u)
            else:
                dfs_hooks.dfs_main_visit_not_invoke(dfs_environ,u)

        dfs_hooks.dfs_main_end(dfs_environ)

        return dfs_environ

    def DFS_visit(self,u,dfs_environ,dfs_hooks):
        dfs_environ.c[u] = 1
        dfs_hooks.dfs_visit_begin(dfs_environ,u)

        for v in \
        dfs_hooks.dfs_visit_vertices_order(dfs_environ,self.neighbours(u)):
            if dfs_environ.c[v] == 0:
                dfs_hooks.dfs_visit_tree_edge_before(dfs_environ,u,v)
                self.DFS_visit(v,dfs_environ,dfs_hooks)
                dfs_hooks.dfs_visit_tree_edge_after(dfs_environ,u,v)
            elif dfs_environ.c[v] == 1:
                dfs_hooks.dfs_visit_back_edge(dfs_environ,u,v)
            else:
                if dfs_environ.d[v] > dfs_environ.d[u]:
                    dfs_hooks.dfs_visit_forward_edge(dfs_environ,u,v)
                else:
                    dfs_hooks.dfs_visit_cross_edge(dfs_environ,u,v)

        dfs_environ.c[u] = 2
        dfs_hooks.dfs_visit_end(dfs_environ,u)

    def compute_bicon_info(self,d,p):
        if self.directed:
            raise NotImplementedError(
                    "Articulations and bridges are supported only for undirected graphs.")
        low = dict([(u,d[u]) for u in self.vertices()])
        b = dict([(u,d[u]) for u in self.vertices()])
        ch = dict([(u,[]) for u in self.vertices()])

        for u in self.vertices():
            for v in self.neighbours(u):
                if p[v] == u: # (u,v) is a TREE edge
                    ch[u].append(v)
                elif p[u] != v and d[v] < d[u]: # (u,v) is a BACK edge
                    w = u
                    b[u] = min(b[u],d[v])
                    w = p[u]
                    while w != v and d[v] < low[w]:
                        low[w] = d[v]
                        b[w] = min(b[w],low[w])
                        w = p[u]

        return low,b,ch

    @staticmethod
    def articulations(d,p,low,ch):
        #FIXME wrong algorithm!
        # if u has more than 1 child and for some child b[v] = d[v] and for
        # other child v b[w] < d[w], then low[u] < d[u], yet T(v) forms a
        # separated component, but this algorithm does not list u as
        # articulation
        for u in low:
            if low[u] == d[u]:
                if p[u] is None:
                    if len(ch[u]) > 1:
                        yield u
                else:
                    if len(ch[u]) > 0:
                        yield u

    @staticmethod
    def bridges(d,p,b,ch):
        #FIXME check correctness, with regard to articulations
        for u,l in b.iteritems():
            if b[u] == d[u] and p[u] is not None:
                yield (u,p[u])

    def __str__(self):
        ret = ""
        first = True
        for u in self.vertices():
            u_neighbours = self.neighbours(u)
            if first:
                first = False
            else:
                ret += "\n"
            ret += "%s: " % u
            ffirst = True
            for v in u_neighbours:
                if ffirst:
                    ffirst = False
                    ret += "%s" % v
                else:
                    ret += ", %s" % v
        return ret

def graph_option_parser():
    from optparse import OptionParser
    parser = OptionParser()
    parser.add_option("-d", "--directed",   action="store_true",
            dest="directed", default=False, help="Graph is directed (default)")
    parser.add_option("-u", "--undirected", action="store_false",
            dest="directed", help="Graph is undirected")

    parser.add_option("-m", "--multigraph", action="store_true", dest="multi",
            default=True, help="Graph is a multigraph")

    return parser
